/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package buscaemamplitude;

import mapa.ProblemaMapa;
import java.util.ArrayList;
import java.util.List;
import numeros.ProblemaNumeros;

/**
 *
 * @author Administrador
 */
public class BuscaEmAmplitude {
    
    private List<Nodo> explorados;
    private List<Nodo> fronteira;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        BuscaEmAmplitude buscaEmAmplitude = new BuscaEmAmplitude();
        Problema problema = new ProblemaNumeros();
        //Problema problema = new ProblemaMapa();
        Nodo resultado = buscaEmAmplitude.buscar(problema);
        if (resultado != null) {
            System.out.println("Custo total: " + resultado.getEstado().getCustoAcumulado());
            System.out.println("Passos:\n");
            List<Nodo> list = new ArrayList<Nodo>();
            while (resultado != null) {
                list.add(0, resultado);
                resultado = resultado.getPai();
            }
            for (Nodo nodo : list) {
                System.out.println(nodo.getEstado().getValor().toString());
            }
        } else {
            System.out.println("Nenhuma solução encontrada!");
        }
    }
    
    public Nodo buscar(Problema problema) {
        
        explorados = new ArrayList();
        fronteira = new ArrayList();
        
        Nodo raiz;
        raiz = new Nodo(new Estado(problema.getEstadoInicial(), 0, 0), null, 0);

        //System.out.println(raiz.getEstado().getValor().toString());

        fronteira.add(raiz);
        
        EstadoObject estadoFinal = problema.getEstadoFinal();
        
        while (!fronteira.isEmpty()) {
            Nodo get = fronteira.get(0);
            fronteira.remove(0);

            if (get.getEstado().getValor().equals(estadoFinal)) {
                return get;
            } else {
                List<Estado> novos = problema.explorar(get.getEstado().getValor());
                
                for (Estado novo : novos) {
                    boolean estadoRepitido = false;

                    //verifica se estado já foi "visitado"
                    for (Nodo nodo : fronteira) {
                        if (nodo.getEstado().getValor().equals(novo.getValor())) {
                            estadoRepitido = true;
                            break;
                        }
                    }
                    if (!estadoRepitido) {
                        for (Nodo nodo : explorados) {
                            if (nodo.getEstado().getValor().equals(novo.getValor())) {
                                estadoRepitido = true;
                                break;
                            }
                        }
                    }

                    //se este estado ainda não foi "visitado", então adiciona à fronteira
                    if (!estadoRepitido) {
                        
                        novo.setCustoAcumulado(novo.getCustoAcumulado() + get.getEstado().getCustoAcumulado());
                        novo.setCustoEstimado(problema.getCustoEstimado(novo.getValor()));
                        
                        float custoTotal = novo.getCustoTotal();                        
                        int i = 0;

                        //insere na fronteira baseado em seu custo total (custo acumulado + custo estimado)
                        while (i < fronteira.size() && custoTotal > fronteira.get(i).getEstado().getCustoTotal()) {
                            i++;
                        }
                        fronteira.add(i, new Nodo(novo, get, get.getNivel() + 1));                      
                        
                    }
                }                
            }
            
            explorados.add(get);
        }
        
        return null;
    }
}
